/**
 *
 */
package datastructure.sort;

import datastructure.search.BinarySearchInsertIndex;

import java.util.Comparator;

/**
 * Description：插入排序
 * Author: zhangc
 * Date：2017/6/19 21:13
 */
public final class InsertSort {

    /**
     * 从第二个元素开始和之前的每一个比较，找到位置之后移动并插入。
     * 从前向后比较，找到插入位置
     * @param array
     * @param <T>
     */
    public static <T extends Comparable<T>> void insertSort(T[] array) {
        T temp;
        int index;
        for (int i = 1; i < array.length; ++i) {
            index = i;
            temp = array[ i ];
            for (int j = 0; j < i; ++j) {
                if (array[ i ].compareTo(array[ j ]) < 0) {
                    index = j;
                    break;
                }
            }
            System.arraycopy(array, index, array, index + 1, i - index);
            array[ index ] = temp;
        }
    }

    /**
     * 从第二个元素开始，从后向前比较，满足就移动，不满足就插入
     *  从后向前比较
     * @param array
     * @param comparator
     */
    public static <T> void insertSort(T[] array, Comparator<T> comparator) {
        T temp;
        int index;
        for (int i = 1; i < array.length; ++i) {
            index = 0;
            temp = array[ i ];
            for (int j = i; j > 0; --j) {
                if (comparator.compare(array[ j - 1 ], temp) > 0)
                    array[ j ] = array[ j - 1 ];
                else {
                    index = j;
                    break;
                }
            }
            array[ index ] = temp;
        }
    }


    /**
     * 通过折半查找，查找插入位置的插入排序
     *
     * @param array
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void insertSortByBinSearch(T[] array) {
        int index;
        T temp;
        for (int i = 1; i < array.length; i++) {
            temp = array[ i ];
            index = BinarySearchInsertIndex.findIndexInsert(array, 0, i - 1, temp);
            System.arraycopy(array, index, array, index + 1, i - index);
            array[ index ] = temp;
        }
    }

}
